package com.mdnote.structure.treebaswe;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/8/29
 * @description 二叉树基础 删除元素
 */
public class BinaryTreeRemove {

    /**
     * 节点
     */
    private static class Node {
        private int value;
        private Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        /**
         * 谦虚遍历
         */
        private void preOrder() {
            System.out.print(this.value + " ");
            if (this.left != null) {
                this.left.preOrder();
            }
            if (this.right != null) {
                this.right.preOrder();
            }
        }

        /**
         * 终须遍历
         */
        private void infixOrder() {
            if (this.left != null) {
                this.left.infixOrder();
            }
            System.out.print(this.value + " ");
            if (this.right != null) {
                this.right.infixOrder();
            }
        }

        /**
         * 后续遍历
         */
        private void postOrder() {
            if (this.left != null) {
                this.left.postOrder();
            }
            if (this.right != null) {
                this.right.postOrder();
            }
            System.out.print(this.value + " ");
        }

        public void remove(int val) {
            // 以当前节点为基准，看看左边的节点是不是想要的
            if (this.left != null && this.left.value == val) {
                this.left = null;
                return;
            }
            // 看看右边的元素是不是想要的
            if (this.right != null && this.right.value == val) {
                this.right = null;
                return;
            }
            if (this.left != null) {
                this.left.remove(val);
            }
            if (this.right != null) {
                this.right.remove(val);
            }
        }

        private void removePlus(int value) {
            if (this.left != null && this.left.value == value) {
                if (this.left.left != null) {
                    this.left = this.left.left;
                } else {
                    this.left = null;
                }
                return;
            }
            if (this.right != null && this.right.value == value) {
                if (this.right.left != null) {
                    this.right = this.right.left;
                } else {
                    this.right = null;
                }
                return;
            }
            if (this.left != null) {
                removePlus(value);
            }
            if (this.right != null) {
                removePlus(value);
            }
        }
    }

    public Node root;

    public BinaryTreeRemove(Node root) {
        this.root = root;
    }

    private void preOrder() {
        root.preOrder();
    }

    private void infixOrder() {
        root.infixOrder();
    }

    private void postOrder() {
        root.postOrder();
    }

    private void remove(int val) {
        if (root != null) {
            if (this.root.value == val) {
                this.root = null;
                return;
            }
            root.remove(val);
        }
    }

    private void removePlus(int val) {
        if (this.root != null) {
            if (this.root.value == val) {
                if (this.root.left != null) {
                    this.root = root.left;
                } else {
                    this.root = null;
                }
            } else {
                removePlus(val);
            }
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node(11);
        Node node2 = new Node(22);
        Node node3 = new Node(33);
        Node node4 = new Node(44);
        Node node5 = new Node(55);


        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);

        BinaryTreeRemove binaryTreeRemove = new BinaryTreeRemove(node1);
        System.out.println("删除前");
        binaryTreeRemove.preOrder();
        System.out.println();
        System.out.println("删除后");
        binaryTreeRemove.removePlus(11);
        binaryTreeRemove.preOrder();
    }
}
